# 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，
# 还有一个 random 指针指向链表中的任意节点或者 null。

# 来源：力扣（LeetCode）
# 链接：https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof

class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random


class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None

        dic = {}
        cur = head
        while cur:
            dic[cur] = Node(cur.val)
            cur = cur.next

        cur = head
        while cur:
            dic[cur].next = dic[cur.next] if cur.next else None
            dic[cur].random = dic[cur.random] if cur.random else None
            cur = cur.next
        return dic[head]


class Solution1:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None

        cur = head
        while cur:
            next = cur.next
            cur.next = Node(cur.val)
            cur.next.next = next
            cur = next

        cur = head
        while cur:
            copy = cur.next
            copy.random = cur.random.next if cur.random else None
            cur = cur.next.next

        cur = head
        res = head.next
        while cur:
            copy = cur.next
            cur.next = copy.next
            copy.next = cur.next.next if cur.next else None
            cur = cur.next

        return res



